#include "heap.h"

// Calculations for heap locations start at 1, but actual heap in memory starts
// at 0, POS is used to access correct element
#define POS(x) (x - 1)

Heap::Heap(int size)
	: tail(1), size(size)
{
	if (size == 0)
		return;
		
	edgeVector.resize(size);
	
	// Malloc is used instead of new so the heap can be resized if needed
	//edgeArray = (Edge*)malloc(sizeof(Edge) * this->size);
	//for (int i = 0; i < this->size; i++)
	//	edgeArray[i] = Edge();
}

void Heap::insert(Edge edge)
{
	// Heap is resized using realloc if needed (not required for the
	// assignment, but a nice to have feature)
	
	/*
	//if (tail >= size)
	//{
		//int oldSize = size;
		//size *= 2;
		//edgeArray = (Edge*)realloc(edgeArray, sizeof(Edge) * size);
		//for (int i = oldSize; i < size; i++)
		//	edgeArray[i] = Edge();

		
#if DEBUG
		//std::cerr << "Reallocing binary heap\n";
#endif
	//}

	//edgeArray[POS(tail)] = edge;
	
	*/
	
	if (tail >= (int) edgeVector.size())
		edgeVector.push_back(edge);
	else
		edgeVector[POS(tail)] = edge;
	
	up(tail, tail / 2);
	tail++;
}

Edge Heap::deleteMin()
{
	if (tail <= 0)
		throw new std::runtime_error("Binary Heap tail is invalid");
	
	// Swaps variables, could simply create a new variable and free some
	// heap memory when enough elements are deleted, but this allows deleteMin
	// to be used for sorting if needed
	std::swap(edgeVector[POS(1)], edgeVector[POS(--tail)]);

	down(1);
	return edgeVector[POS(tail)];
}

// Sorts using iterative approach, another approach would be to call deleteMin
// continuously to get a heap in max sorted order (this is about 2% faster and
// gives a min sorted array, which is better for the assignment)
void Heap::sort(vector<Edge> &edgeVector)
{
	this->edgeVector = edgeVector;
	this->size = (int) edgeVector.size();
	tail = size + 1;
	heapify();

	for (int i = 0; i < size; i++)
	{
		std::swap(this->edgeVector[POS(1)], this->edgeVector[POS(--tail)]);
		downIterative(1);
	}
	
	//this->edgeVector = 0;
	edgeVector = this->edgeVector;
	this->size = 0;	
	tail = 0;
}

// Iterative version of down, for comparison
void Heap::downIterative(int start)
{
	int smallest = tail + 1;
	int root = start;
	int left = root * 2;
	int right = left + 1;
	
	while (left < tail)
	{
		if (right < tail && edgeVector[POS(right)].cost > edgeVector[POS(left)].cost)
			smallest = right;
		else
			smallest = left;
		if (edgeVector[POS(root)].cost < edgeVector[POS(smallest)].cost)
		{
			std::swap(edgeVector[POS(root)], edgeVector[POS(smallest)]);
			root = smallest;
			left = root * 2;
			right = left + 1;
		}
		else
		{
			return;
		}
	}
}

void Heap::up(int left, int right)
{
	if (right == 0) return;

	if (edgeVector[POS(left)].cost < edgeVector[POS(right)].cost)
	{
		std::swap(edgeVector[POS(left)], edgeVector[POS(right)]);
		up(right, right / 2);
	}
}

// Recursive version of down, for comparison
void Heap::down(int pos)
{
	int left = pos * 2;
	int right = left + 1;

	if (left < tail && right < tail)
	{
		if (edgeVector[POS(pos)].cost > edgeVector[POS(left)].cost ||
			edgeVector[POS(pos)].cost > edgeVector[POS(right)].cost)
		{
			float val = std::min(edgeVector[POS(left)].cost, edgeVector[POS(right)].cost);

			if (val == edgeVector[POS(left)].cost)
			{
				std::swap(edgeVector[POS(pos)], edgeVector[POS(left)]);
				down(left);
			}
			else
			{
				std::swap(edgeVector[POS(pos)], edgeVector[POS(right)]);
				down(right);
			}
		}
	}
	else if (left < tail && edgeVector[POS(pos)].cost > edgeVector[POS(left)].cost)
	{
		std::swap(edgeVector[POS(pos)], edgeVector[POS(left)]);
		down(left);
	}
	else if (right < tail && edgeVector[POS(pos)].cost > edgeVector[POS(right)].cost)
	{
		std::swap(edgeVector[POS(pos)], edgeVector[POS(right)]);
		down(right);
	}
}

// Uses the iterative approach, should use recursive down if deleteMin is
// chosen for sorting instead
void Heap::heapify()
{
	int start = size / 2;
	
	while (start > 0)
		downIterative(start--);
}

#undef POS
